1. Field of the Invention
The present invention relates to an exponentiation remainder operation circuit, and particularly relates to an exponentiation remainder operation circuit to operate multiple-digit adjusting numbers used in public key code systems, for example.
2. Description of the Related Art
Conventionally, this type of exponentiation remainder operation circuit is used for public key cryptosystems, and particularly for RSA codes, as disclosed in "A generalization of Brickell's algorithm for fast modular multiplication" (Bit, vol. 28, 1988). "RSA" means a password developed by R. L. Rivest, A. Shamir and L. Adleman as disclosed in U.S. Pat. No. 4,405,829.
FIG. 7 is a block diagram showing an example of a conventional exponentiation remainder operation circuit. The exponentiation remainder operation to be executed here is "A=X.sup.E mod N", which is to determine the remainder A of the division where the value obtained by exponentiation of parameter X with parameter E is divided by parameter N. It is supposed here that parameter X is set at a register X 608, parameter E at a shift register E 617 and two's compliment of parameter N at a register K 612 in advance. All parameters have n bits.
A selector D 601 outputs 0 or 1 to a register D 602 depending on the value of a signal SELD 623: it outputs a signal M627 when the signal SELD 623 is 0, and the value 0 when the signal SELD 623 is 1. The register D 602 stores the signal input from the selector D 601 according to a signal WRD 624 and outputs the signal value to a one-bit left shifter 603 and a selector A 606.
The one-bit left shifter 603 shifts the signal input from the register D602 to the left by one bit and outputs the shifted signal value to a first adder 603. For the least significant bit of the shifted signal, the value 0 is output.
The selector A 606 outputs, to a register A 607, the data from the register D602 when a signal SELA618 is 0 and the value 1 when the signal SELA618 is 1. The register A607 stores the signal input from the selector A606 according to a signal WRA 619 and outputs the stored value to an (A.times.s) multiplier 611 and to a selector B 609.
In other words, the register A607 holds the intermediate and final results of the exponentiation remainder operation. The register X 608 has the parameter X.
The selector B 609 works according to the value of a signal SELB 620 and outputs, to a shift register B610, the data from the register A 607 when the signal is 0 and the data from the register X 608 when the signal is 1. The shift register B 610 stores the signal input from the selector B609 according to a signal WRB 621. According to a signal SFTB622, it also shifts the stored value to the left by one bit and outputs the shifted out signal to the (A.times.s) adder 611.
The (A.times.s) adder 611 makes multiplication using the signal input from the register A607 and the signal input from the shift register B 610 and outputs the result to the first adder 604. Since the actual input value from the shift register B 610 is limited to 0, 1 or 2, the multiplier device can be of a simple configuration using bit shifting.
The first adder 604 adds the input from the one-bit left shifter 603 to the input from the (A.times.s) multiplier 611 and outputs the result as a signal m626 to a second adder 605 and a (K.times.(a.div.N)) operator 613. The register K 612 holds two's compliment of parameter N.
The (K.times.(a.div.N)) operator 613 divides the signal m626 input from the first adder by parameter N, multiplies by its quotient the signal input from the register K 612 and outputs the result to the second adder 605 as a signal tK628.
The second adder 605 adds the input from the first adder 604 to the signal tK628 input from the (K.times. (a.div.N)) operator 613 and outputs the result as the signal M627 to the selector D 601. The shift register E 617 having parameter E as initial setting shifts the parameter value to the left by one bit according to the signal SFTE625 and outputs the shifted out signal to a CPU 614.
According to the signal input from the shift register E 617, a first count 615 and a second count 616 in the CPU 614 and the preset control program, the CPU 614 outputs the signals SELA618, WRA619, SELB620, WRB621, SFTB622, SELD623, WRD624 and SFTE625.
Referring next to FIGS. 8 and 9, the operation of the CPU 614 in the conventional system will be described below.
Firstly, the value 1 is given for the signal SELA618 and the signal WRA619 so as to initialize and provide "1" to the register A 607, which holds the exponentiation remainder operation result (Step 701). The first count 615 is initialized to 0 (Step 702). Then, the signal SELB 620 is set to 0 and the signal WRB 621 to 1, which causes the content of the register A 607 to be copied to the shift register B 610 (Step 703). Then, the subroutine "mulmod" is executed, i.e. the remainder of the division where the multiplication result of the values in the register A 607 and the shift register B 610 is divided by parameter N is sent to the register A 607 (Step 704). Thus, the content of the register A 607 is squared.
Then, the signal SFTE 624 is set to 1 so as to shift the content of the shift register E 617 to the left by one bit (Step 705). Then the bit shifted out from the shift register E 617 is checked to see whether or not it is 1 (Step 706). When the shifted out bit is 1, the value 1 is output for the signal SELB620 and 1 to the signal WRB621. This causes the content of the register X 608 to the shift register B 610 (Step 707). Then, the subroutine MULMOD is executed (Step 708). Thus, when the bit shifted out from the shift register E 617 is 1, the content of the register A 607 is multiplied by parameter X. When the shifted out bit is 0, the multiplication by X is not executed.
Here, the first count 615 is increased by one (Step 709), and then checked to see whether or not the first count 615 is n (Step 710). When the first count 615 is not n, the system goes back to Step 703. Thus, the processes of Steps 703 to 709 are repeated for n times, which corresponds to the bit length of the parameters. When the first count 615 is n, the system terminates the processing. Upon termination, the register A 607 has the exponentiation remainder operation result.
The subroutine mulmod comprises the operation as described below.
Firstly, the signal SELD 623 is set to 1 and the signal WRD 624 to 1 so that the content of the register D is initialized to have 0 (step 801). The second count 616 is also initialized to 0 (Step 802). Then, the signal SFTB 622 is set to 1 and the content of the shift register B 610 is shifted to the left by one bit (Step 803). Thus, the output m626 of the first adder becomes (2.times. Content of register D 602+ Content of register A 607.times. shifted out value from the shift register B 610).
At the same time, the output M627 from the second adder becomes (signal m626+ content of register K 612.times. (quotient obtained by division of signal m626 by parameter N)).
Then, the signal SELD 623 is set to 1 and the signal WRD 624 to 1, so that the second adder output M627 is written to the register D 602 (Step 804). Here, the second count number 616 is increased by one (Step 805), and checked to see whether or not the second count number 616 is (n+8) (Step 806). If not, the system reruns to Step 803. Thus, the processes of Steps 803 to 806 are repeated for (n+8) times, which is the value obtained by adding 8 to the bit length n of the parameters. If the second count number 616 is (n+8), the value 0 is given as the signal SELA 618 and as the signal WRA 620, which causes the content of the register D 602 to be copied to the register A 607 (Step 807). Then, the system returns to the main routine. At this stage, the content of the register A 607 is the remainder of the division by parameter N of the multiplication result of the value in the register A 607 and the shift register B 610.
Now referring to FIGS. 10, 20, 21 and 22, the register D 602, the register A 607, the shift register B 610 and the one-bit left shifter are described.
As shown in FIG. 10, the register D 602 comprises a register DH 901 with a bit length of (n+10) and a register DL 902 with a bit length of (n+10). According to the signal WRD624, they store the signal input from the selector D 601 individually, and output their contents individually. The register DH 901 and the register DL 902 assign the most significant bit to the bit (n+1) and then the following bits to n, (n-1) and so on, so that the least significant bit is assigned to the eighth bit below 0. Unless otherwise specified, the signals with the same bit numbers hereafter correspond each other.
As shown in FIG. 20, the register A 607 comprises a register AH 903 with a bit length of n and a register AL 904 with a bit length of n. According to the signal WRA 619, they individually store the input signal and individually output their contents. The register AH 903 and the register AL 904 assign the most significant bit to the bit (n-9) and the following bits to bit (n-10), (n-11) and so on, to have the least significant bit at the eighth bit below 0.
As shown in FIG. 21, the shift register B 610 comprises a shift register BH 905 having a bit length of n and a shift register BL 906 having a bit length of n and an n-bit-long one-bit right shifter 907. The n-bit-long one-bit right shifter 907 shifts the input signal to the right by one bit and outputs the shift result to the shift register BH 905, with placing 0 for the most significant bit.
The shift register BH 905 and the shift register BL 906 individually store the input signals according to the signal WRB621 and upon the signal SFTB622, shift the contents to the left by one bit. Then, the shifted out bits are output separately. Specifically, when the shift register BL 906 shifts out the bit k, the shift register BH 905 outputs the bit after one-bit shifting to the right with the n-bit-long one-bit right shifter 907, or the bit (k+1) of the input signal. The input signal of the bit k in the shift register B is represented by the value of the bit (k+1).times.2.
As shown in FIG. 22, the one-bit left shifter A 601 comprises wire connections only, as shown in a block 908. The bit length of the one-bit left shifter A601 is m, as shown in the figure. With the configuration in the figure, the one-bit left shifter A 601 can output the input signal for the bit k to the bit (k+1). It outputs 0 to the least significant bit. An m-bit-long one-bit right shifter can be similarly defined. Specifically, an m-bit-long one-bit right shifter outputs the bit k of the input signal to the bit (k-1), with outputting 0 for the most significant bit.
FIG. 11 shows a block diagram of an r-bit-long delay adder, used in the first and the second adders 604 and 605. An r-bit-long AND operator 1001 outputs the AND of the bit k in the r-bit input b and the bit K in the r-bit input c to the bit k.
An r-bit-long XOR operator 1002 outputs the exclusive OR of the bit k in the r-bit input b and the bit k in the r-bit input c to the bit k. The r-bit-long one-bit left shifter 1003 shifts the data from the r-bit-long AND operator 1001 to the left by one bit and outputs the result to an r-bit-long OR operator 1004.
The r-bit-long OR operator 1004 outputs the 0R of the bit k in the r-bit input data a and the bit k in the r-bit input data from the r-bit-long one bit left shifter 1003 to the bit k. An r-bit-long AND operator 1005 outputs the AND of the bit k in the input from the r-bit-long OR operator 1004 and the bit k of the data from the r-bit-long XOR operator 1002.
An r-bit-long XOR operator 1006 outputs the exclusive OR of the bit k in the input data from the r-bit-long OR operator 1004 and the bit k in the data from the r-bit-long XOR operator 1002 as the bit k of r-bit output signal L.
An r-bit-long one-bit left shifter 1007 shifts the data from the r-bit-long AND operator 1005 to the left by one bit and outputs as r-bit output signal H. Note that the r-bit-long one-bit left shifters 1003 and 1007 have the same configuration as the one-bit left shifter A601 of FIG. 22 except for the bit length. The sum of the outputs H and L from the r-bit-long delay circuit with the configuration as described above is represented as the output HL. The value of HL is equal to the addition result obtained by (input a+input b)+input c. Further, as easily understood from the configuration, the input signal passes through only three logical operation units before attaining the outputs H and L. When compared with ordinary adders with carry transmission, it has delay time for only three steps of logical units, which enables much more rapid addition operation.
Referring next to FIG. 12, the configurations and procedures at the (A.times.s) multiplier 613 and the first adder 604 will be described below.
The procedure at the (A.times.s) multiplier 613 is as follows. An (n+1)-bit-long one-bit left shifter 1101 has 0 at the most significant bit and the signal from the register AL 904 at the lower n bits and outputs the value with one bit shifting to the left to a selector 1102.
The selector 1102 receives the shifted out bit of the shift register BH 905 at bit 1 and the shifted out bit from the shift register BL 906 at bit 0 of the selection signal. The output from the selector 1102 to a (n+10)-bit-long delay adder 1105 depends on the value represented by bits 1 and 2 of the selection signal. When the value is 0, the selector 1102 outputs 0 for (n+1) bits; when it is 1, the selector 1102 outputs the most significant bit and the input data from the register AL 904 to the lower n bits, and when it is 2, the selector 1102 outputs the input signal from the (n+1)-bit-long one-bit left shifter 1101 for the lower (n+1) bit of the input c at the (n+10)-bit-long delay adder 1105. In this conventional example, the sum of the shifted out bits does not become 3.
An (n+1)-bit left shifter 1103 and as selector 1104 operates with the similar procedure except that their input signal is from register AH 904 and the output is sent to the (n+10)-bit-long delay adder 1106. Thus, the result of multiplication where the value from the register A 607 is multiplied by the shifted out bit value from the shift register B 610 can be output.
The first adder 603 has the configuration and procedure as described below. The (n+10)-bit-long delay adder 1105 receives, as the input a, the value obtained by shifting the value in the register DH 901 to the left by one bit with the one-bit left shifter 603, i.e. the signal twice the value in the register DH 901. As the input b, it receives the value obtained by shifting the value in the register DL 902 to the left by one bit with the one-bit left shifter 603, i.e. the signal twice the value in the register DL 902. As the input c, it receives 0 for the higher nine bits and the output signal from the selector 1102 for the lower (n+1) bits.
The (n+10)-bit-long delay adder 1106 receives, as the input a, the output signal H from the (n+10)-bit-long delay adder 1105 and as the input b, the output signal L from the (n+10)-bit-long delay adder 1105, and as the input c, 0 for the higher nine bits and the output signal from the selector 1104 for the lower (n+1) bits. The output signal H is referred to as mH, the output signal L as mL, and the mH and mL are collectively referred to as the signal m626.
Under the operation at the r-bit-long delay adder as above, the result of the outputs mL and mH becomes equal to the value obtained by this formula: Content of register D 602.times.2+ Content of register A 607.times. shifted out bits from shift register B.
Referring now to FIG. 13, the second adder 605 has the configuration and procedure as described below.
An (n+8)-bit-long delay adder 1201 receives, as the input a, the lower (n+8) bits of the output mH from the (n+10)-bit-long delay adder 1106 and as the input b, the lower (n+8) bits of the output mL from the (n+10)-bit-long delay adder 1106 and as the input c, the signal tK628 for the higher n bits and 0 for the lower 8 bits respectively. The most significant bit of the output H and the most significant bit of the output L from the (n+8)-bit-long delay adder 1201 are input to an XOR operator 1202. The XOR operator 1202 outputs the exclusive OR of the most significant bit of the output H and the most significant bit of the output L from the (n+8)-bit-long delay adder 1201.
The higher three bits of the output signal MH 1203 with a length of (n+10) bits always have 0, and the lower (n+7) bits have the values at the lower (n+7) bits of the output H from the (n+8)-bit-long delay adder 1201.
The higher two bits of the output signal ML 1204 are always 0, the third bit from the most significant bit has the output signal from the XOR operator 1202 and the lower (n+7) bits have the same values as the lower (n+7) bits of the output L from the (n+8)-bit-long delay adder 1201.
The signal MH 1203 and the signal ML 1204 are collectively referred to as the signal M627. The value obtained by adding the signal MH1203 and the signal ML1204 is the same as the lower (n+8) bits of (mH+mL)+tK.
Referring now to FIG. 14, the configuration and procedure for the (K.times.(a+N)) operator 613 are described below.
A six-bit-long one-bit left shifter 1315 outputs, to a six-bit-long delay adder 1302, the higher six bits of the output from the register K 612 with shifting it to the left by one bit. The six-bit-long delay adder 1301 receives, as the input a, the higher six bits of the signal mH1107 and as the input b, the higher six bits of the signal mL1108, and as the input c, the higher six bits of the output signal from the register K 612 respectively. Bits 5 and 4 of the output H are sent to a two-bit adder 1305 and bit 3 to an AND operator 1303; From the output L, bits 5 and 4 are sent to a two-bit adder 1307 and bit 3 to the AND operator 1303.
The six-bit-long delay adder 1302 receives, as the input a, the higher six bits of the signal mH1107 and as the input b, the higher six bits of the signal mL1108, and as the input c, the output signal from the six-bit-long one-bit left shifter 1315 respectively. Bits 5 and 4 of the output H are sent to a two-bit adder 1306 and bit 3 to the AND operator 1304; bits 5 and 4 of the output L are sent to a two-bit adder 1308 and bit 3 to the AND operator 1304.
The AND operator 1303 outputs, to the two-bit adder 1305, the AND of bit 3 of the output H and bit 3 of the output L from the six-bit-long delay adder 1301. The AND operator 1304 outputs, to the two-bit adder 1306, the AND of bit 3 of the output H and bit 3 of the output L from the six-bit-long delay adder 1302.
The two-bit adder 1305 outputs, to the two-bit adder 1307, a two-bit result of the addition where a two-bit value represented by bits 5 and 4 of the output H from the six-bit-long delay adder 1301 is added to another two-bit value having 0 at bit 1 and the output from the AND operator 1303 at bit 0.
The two-bit adder 1306 outputs, to the two-bit adder 1308, a two-bit result of the addition where a two-bit value represented by bits 5 and 4 of the output H from the six-bit-long delay adder 1302 is added to another two-bit value having 0 at bit 1 and the output value from the AND operator 1304 at bit 0. The two-bit adder 1307 outputs, to a comparator (a=1) 1309, a two-bit result of the addition where a two-bit value represented by bits 5 and 4 of the output L from the six-bit-long delay adder 1301 is added to the output signal from the two-bit adder 1305.
The two-bit adder 1308 outputs, to a comparator (a=2) 1310, a two-bit result of the addition where a two-bit value represented by bits 5 and 4 of the output L from the six-bit-long delay adder 1302 is added to the output signal from the two-bit adder 1306.
The comparator (a=1) 1309 outputs, to the AND operator 1312, the value 1 when the input a from the two-bit adder 1307 is equal to 1 and the value 0 when the input a is not equal to 1. The comparator (a=2) 1310 outputs, to a NOT operator 1311 and to bit 1 of the selection signal for the selector 1314, the value 1 when the input a from the two-bit adder 1308 is equal to the value 2 and 0 when it is not equal to 2.
The NOT operator 1311 outputs the logical NOT of the input from the comparator (a=2) 1310 to the AND operator 1312.
The AND operator 1312 outputs, to bit 0 of the selection signal for the selector 1314, the AND of the input from the comparator (a=1) 1309 and the NOT operator 1311. Thus, the two-bit value represented by bits 1 and 0 of the control signal input for the selector 1314 becomes 2 when the value obtained by adding the AND of bit 3 of the operation result H and bit 3 of the operation result L to the higher two bits of the result of (mH+mL)+K.times.2 is 2. It becomes 1 when the value obtained by adding the AND of bit 3 of the operation result H and bit 3 of the operation result L to the higher two bits of the operation result of (mH+mL)+K is equal to 1. It becomes 0 for other cases. This is the quotient of the division where the signal m626 is divided by the parameter N. In this conventional example, the quotient value is limited to 0, 1 and 2.
An n-bit-long one-bit left shifter 1313 shifts the signal input from the register K 612 to the left by one bit and outputs the shifted value to the selector 1314. The selector 1314 outputs, as the signal tK628, the signal input from the n-bit-long one-bit left shifter 1313 when the selection signal is 2 and the input from the register K 612 when it is 1 and 0 when it is 0.
In other words, the value of the signal tK 628 is equal to the result of multiplication where the value at the register K 612 is multiplied by the value of the selection signal. Thus, the signal tK627 is equal to the value obtained by multiplying the content of the register K 612 by the quotient of the division where the signal m626 is divided by parameter N.
Conventionally, an n-bit-long exponentiation remainder operation circuit makes all operations with a unit of n bits. This means that, for n-bit long exponentiation, the subroutine MULMOD is required to be performed for 2.times.n times at most, because, as shown in FIG. 8, the subroutine MULMOD is executed in Steps 704 and 708 in the loop processing for n times.
Therefore, if the value of n is large, operations must be repeated for many times. In the case of RSA coding, for example, exponentiation remainder operation for 512 bits, 1024 times of multiplication remainder operations may be required at most. Described below is such a system where the number of system clocks n is 512, with considering one step in the flowcharts of FIGS. 8 to be one clock.
The subroutine MULMOD is 2+(n+8).times.4+1, and in this case, it has 2083 clocks (2+(512+8).times.4+1=2083). The main routine may have, at the longest, a length of 2.times.n.times.(6+MULMOD+MULMOD), which is, in this case, 2+512.times.(6+2083+2083)=2134018 clocks. Thus, a conventional exponentiation remainder operation circuit requires a quite lengthy processing time when the operation bit length n is a large value.